package org.everyday;

import cn.hutool.core.lang.Assert;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: Tang World
 * @Date: 6/9/2022 下午12:30
 */
public class L828H {
    public static void main(String[] args) {
        int aba = new L828H().uniqueLetterString("ABA");
        Assert.isTrue(aba == 8);
        int abc = new L828H().uniqueLetterString("ABC");
        Assert.isTrue(abc == 10);
        int aaa = new L828H().uniqueLetterString("AAA");
        Assert.isTrue(aaa == 3);
        int LEETCODE = new L828H().uniqueLetterString("LEETCODE");
        Assert.isTrue(LEETCODE == 92);

    }

    public int uniqueLetterString(String s) {
        // 根据数学，计算每一个值的贡献
        //一个字符，在前一个相同字符和后一个相同字符的开区间内，左半边任选一个点，右半边人选一个点的总共组合数
        // 即该字符对res的贡献
        // 特殊情况为没有前后相同节点时，在-1和length处添加一个相同节点。
        Map<Character, List<Integer>> index = new HashMap<Character, List<Integer>>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!index.containsKey(c)) {
                index.put(c, new ArrayList<Integer>());
                index.get(c).add(-1);
            }
            index.get(c).add(i);
        }
        int res = 0;
        for (Map.Entry<Character, List<Integer>> entry : index.entrySet()) {
            List<Integer> arr = entry.getValue();
            arr.add(s.length());
            for (int i = 1; i < arr.size() - 1; i++) {
                res += (arr.get(i) - arr.get(i - 1)) * (arr.get(i + 1) - arr.get(i));
            }
        }
        return res;
    }

}
